import copy
from collections import deque, defaultdict


def hash(status: list):
    ans = []
    for i in range(3):
        for j in range(3):
            ans.append(status[i][j])
    return tuple(ans)


def check(status):
    for i in range(3):
        for j in range(3):
            if i == j == 2: return True
            if status[i][j] != i * 3 + j + 1:
                return False
    return False


def solve(init_status):
    min_distance = defaultdict(lambda: float('inf'))
    que = deque()  # 初始状态 无操作
    que.append([init_status, []])
    min_distance[hash(init_status)] = 0
    while que:
        curr_status, ways = que.popleft()
        if check(curr_status):
            return ways
        if min_distance[hash(curr_status)] < len(ways):
            continue
        # 找到 0 位置
        for i in range(3):
            for j in range(3):
                if curr_status[i][j] == 0:
                    cx, cy = i, j
                    break
        for nx, ny in [(cx + 1, cy), (cx - 1, cy), (cx, cy + 1), (cx, cy - 1)]:
            if nx < 0 or nx >= 3: continue
            if ny < 0 or ny >= 3: continue
            next_status = copy.deepcopy(curr_status)
            next_ways = copy.copy(ways) + [next_status[nx][ny]]
            next_status[cx][cy], next_status[nx][ny] = next_status[nx][ny], next_status[cx][cy]
            if min_distance[hash(next_status)] < len(next_ways): continue
            min_distance[hash(next_status)] = len(next_ways)
            que.append([next_status, next_ways])
    return -1


if __name__ == '__main__':
    r = solve([[0, 5, 3], [8, 7, 2], [1, 4, 6]])
    if r == -1:
        print("无解")
    else:
        print("请按如下操作 点击拼图的编号")
        print(f"最少需要操作{len(r)}步 顺序为{'->'.join(map(str, r))}")
